home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Icon 8.1 / msm-1 / common.sit / strtbl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-19  |  4.9 KB  |  220 lines  |  [TEXT/MPS ]
  1. /*
  2.  * The functions in this file maintain a hash table of strings and manage
  3.  *   string buffers.
  4.  */
  5. #include "::h:gsupport.h"
  6.  
  7. /*
  8.  * Prototype for static function.
  9.  */
  10. hidden int streq  Params((int len,char *s1,char *s2));
  11.  
  12. /*
  13.  * Entry in string table.
  14.  */
  15. struct str_entry {
  16.    char *s;                 /* string */
  17.    int length;              /* length of string */
  18.    struct str_entry *next;
  19.    };
  20.  
  21. #define SBufSize 1024                     /* initial size of a string buffer */
  22. #define StrTblSz 149                      /* size of string hash table */
  23. static struct str_entry **str_tbl = NULL; /* string hash table */
  24.  
  25. /*
  26.  * init_str - initialize string hash table.
  27.  */
  28. novalue init_str()
  29.    {
  30.    int h;
  31.  
  32.    if (str_tbl == NULL) {
  33.       str_tbl = (struct str_entry **)alloc((unsigned int)(StrTblSz *
  34.          sizeof(struct str_entry *)));
  35.       for (h = 0; h < StrTblSz; ++h)
  36.          str_tbl[h] = NULL;
  37.       }
  38.    }
  39.  
  40. /*
  41.  * free_stbl - free string table.
  42.  */
  43. novalue free_stbl()
  44.    {
  45.    struct str_entry *se, *se1;
  46.    int h;
  47.  
  48.    for (h = 0; h < StrTblSz; ++h)
  49.       for (se = str_tbl[h]; se != NULL; se = se1) {
  50.          se1 = se->next;
  51.          free((char *)se);
  52.          }
  53.          
  54.    free((char *)str_tbl);
  55.    str_tbl = NULL;
  56.    }
  57.  
  58. /*
  59.  * init_sbuf - initialize a new sbuf struct, allocating an initial buffer.
  60.  */
  61. novalue init_sbuf(sbuf)
  62. struct str_buf *sbuf;
  63.    {
  64.    sbuf->size = SBufSize;
  65.    sbuf->frag_lst = (struct str_buf_frag *)alloc((unsigned int)
  66.        (sizeof(struct str_buf_frag) + (SBufSize - 1)));
  67.    sbuf->frag_lst->next = NULL;
  68.    sbuf->strtimage = sbuf->frag_lst->s;
  69.    sbuf->endimage = sbuf->strtimage;
  70.    sbuf->end = sbuf->strtimage + SBufSize;
  71.    }
  72.  
  73. /*
  74.  * clear_sbuf - free string buffer storage.
  75.  */
  76. novalue clear_sbuf(sbuf)
  77. struct str_buf *sbuf;
  78.    {
  79.    struct str_buf_frag *sbf, *sbf1;
  80.  
  81.    for (sbf = sbuf->frag_lst; sbf != NULL; sbf = sbf1) {
  82.       sbf1 = sbf->next;
  83.       free((char *)sbf);
  84.       }
  85.    sbuf->frag_lst = NULL;
  86.    sbuf->strtimage = NULL;
  87.    sbuf->endimage = NULL;
  88.    sbuf->end = NULL;
  89.    }
  90.  
  91. /*
  92.  * new_sbuf - allocate a new buffer for a sbuf struct, copying the partially
  93.  *   created string from the end of full buffer to the new one.
  94.  */
  95. novalue new_sbuf(sbuf)
  96. struct str_buf *sbuf;
  97.    {
  98.    struct str_buf_frag *sbf;
  99.    char *s1, *s2;
  100.  
  101.    /*
  102.     * The new buffer is larger than the old one to insure that any
  103.     *  size string can be buffered.
  104.     */
  105. #if IntBits == 16
  106.    unsigned int oldsize = sbuf->size;
  107.    sbuf->size += (sbuf->size/2);
  108.    if (sbuf->size < oldsize) {        /* check for overflow */
  109.       sbuf->size = MaxBlock;
  110.       }
  111. #else                    /* IntBits == 16 */
  112.    sbuf->size *= 2;
  113. #endif                    /* IntBits == 16 */
  114.  
  115.    s1 = sbuf->strtimage;
  116.    sbf = (struct str_buf_frag *)alloc((unsigned int)
  117.        (sizeof(struct str_buf_frag) + (sbuf->size - 1)));
  118.    sbf->next = sbuf->frag_lst;
  119.    sbuf->frag_lst = sbf;
  120.    sbuf->strtimage = sbf->s;
  121.    s2 = sbuf->strtimage;
  122.    while (s1 < sbuf->endimage)
  123.       *s2++ = *s1++;
  124.    sbuf->endimage = s2;
  125.    sbuf->end = sbuf->strtimage + sbuf->size;
  126.    }
  127.  
  128. /*
  129.  * spec_str - install a special string (null terminated) in the string table.
  130.  */
  131. char *spec_str(s)
  132. char *s;
  133.    {
  134.    struct str_entry *se;
  135.    register char *s1;
  136.    register int l;
  137.    register int h;
  138.  
  139.    h = 0;
  140.    l = 1;
  141.    for (s1 = s; *s1 != '\0'; ++s1) {
  142.      h += *s1 & 0377;
  143.      ++l;
  144.      }
  145.    h %= StrTblSz;
  146.    for (se = str_tbl[h]; se != NULL; se = se->next) 
  147.       if (l == se->length && streq(l, s, se->s))
  148.          return se->s;
  149.    se = NewStruct(str_entry);
  150.    se->s = s;
  151.    se->length = l;
  152.    se->next = str_tbl[h];
  153.    str_tbl[h] = se;
  154.    return s;
  155.    }
  156.  
  157. /*
  158.  * str_install - find out if the string at the end of the buffer is in
  159.  *   the string table. If not, put it there. Return a pointer to the
  160.  *   string in the table.
  161.  */
  162. char *str_install(sbuf)
  163. struct str_buf *sbuf;
  164.    {
  165.    int h;
  166.    struct str_entry *se;
  167.    register char *s;
  168.    register char *e;
  169.    int l;
  170.  
  171.    AppChar(*sbuf, '\0')   /* null terminate the buffered copy of the string */
  172.    s = sbuf->strtimage;
  173.    e = sbuf->endimage;
  174.  
  175.    /*
  176.     * Compute hash value.
  177.     */
  178.    h = 0;
  179.    while (s < e)
  180.      h += *s++ & 0377;
  181.    h %= StrTblSz;
  182.    s = sbuf->strtimage;
  183.    l = e - s;
  184.    for (se = str_tbl[h]; se != NULL; se = se->next) 
  185.       if (l == se->length && streq(l, s, se->s)) {
  186.          /*
  187.           * A copy of the string is already in the table. Delete the copy
  188.           *  in the buffer.
  189.           */
  190.          sbuf->endimage = s;
  191.          return se->s;
  192.          }
  193.  
  194.    /*
  195.     * The string is not in the table. Add the copy from the buffer to the
  196.     *  table.
  197.     */
  198.    se = NewStruct(str_entry);
  199.    se->s = s;
  200.    se->length = l;
  201.    sbuf->strtimage = e;
  202.    se->next = str_tbl[h];
  203.    str_tbl[h] = se;
  204.    return se->s;
  205.    }
  206.  
  207. /*
  208.  * streq - compare s1 with s2 for len bytes, and return 1 for equal,
  209.  *  0 for not equal.
  210.  */
  211. static int streq(len, s1, s2)
  212. register int len;
  213. register char *s1, *s2;
  214.    {
  215.    while (len--)
  216.       if (*s1++ != *s2++)
  217.          return 0;
  218.    return 1;
  219.    }
  220.